// https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/
// Created by ade on 2022/8/2.
//
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> res;

    int maxLevelSum(TreeNode *root) {
        int height = getHeight(root);
        res.resize(height);
        dfs(root, 0);
        int maxSum = INT_MIN;
        int maxLevel = 0;
        for (int i = 0; i < res.size(); i++) {
            if (res[i] > maxSum) {
                maxLevel = i;
                maxSum = res[i];
            }
        }
        return maxLevel + 1;
    }

    int getHeight(TreeNode *root){
        if(!root) return 0;
        return max(getHeight(root->left), getHeight(root->right)) + 1;
    }


    void dfs(TreeNode *root, int index) {
        if (root) {
            if (res.size() < index) {
                res[index] = root->val;
            } else {
                res[index] += root->val;
            }
            dfs(root->left, index + 1);
            dfs(root->right, index + 1);
        }
    }
};

int main() {
    Solution so;
    int a = so.maxLevelSum(root);
    cout << a << endl;
    return 0;
}